#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.empty()){
            return result;
        }
        if(nums.size()==1){
            return {{nums[0]}};
        }
        for(int i = 0;i<nums.size();++i){
            vector<int> tempNums = nums;
            int a = *(tempNums.begin()+i);
            tempNums.erase(tempNums.begin()+i);
            vector<vector<int>> sonResult =  permute(tempNums);
            for(int j = 0;j<sonResult.size();++j){
                sonResult[j].insert(sonResult[j].begin(),a);
                result.push_back(sonResult[j]);
            }
            
        }
        return result;
    }
};

int main(){
    Solution S;
    vector<int> nums = {1,2,3};
    vector<vector<int>> result = S.permute(nums);
    return 0;
}